package com.cn.why.springcloudskills.FaceTest;
import java.util.*;

/**
 * 关于数组的排序算法练习
 */

public class Sort {
    static Integer[] arr = {3,12,43,55,26,45,67,79,25,80,28,6,81,22,35,13};
    //1.最简单的冒泡排序
    public static void  bubblingSort(Integer[] arr1){
        int temp = 0;
        for (int a = 0; a<arr1.length;a++){
            for (int b= a+1;b<arr1.length;b++){
                if (arr1[a] > arr1[b]) {
                    temp = arr1[a];
                    arr1[a] = arr1[b];
                    arr1[b] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr1));
    }

    /**
     * 插入排序法
     * @param arr1
     */
    public static void insertSort(Integer[] arr1){
        //思想：从数组的第二个数开始插入遍历
        for (int a = 1;a<arr1.length;a++){
            int temp = a;
                while (temp>0 && arr1[temp] < arr1[temp-1]){
                    int tee = arr1[temp - 1];
                    arr1[temp-1] = arr1[temp];
                    arr1[temp] = tee;
                    temp--;
                }
        }
        System.out.println(Arrays.toString(arr1));
    }

    /**
     * 快速排序算法（相对于插入和冒泡效率较高，思想：类似于分而治之，拆分后排序（拆分后的左边都小于右边））
     * static Integer[] arr = {3,12,43,55,26,45,67,79,25,80,28,6,81,22,35,13};
     * @param
     */
    public static void quiklySort(Integer[] array,int left,int right){
        if(left > right) {
            return;
        }
        // base中存放基准数
        int base = array[left];
        int i = left, j = right;
        while(i != j) {
            // 顺序很重要，先从右边开始往左找，直到找到比base值小的数
            while(array[j] >= base && i < j) {
                j--;
            }

            // 再从左往右边找，直到找到比base值大的数
            while(array[i] <= base && i < j) {
                i++;
            }

            // 上面的循环结束表示找到了位置或者(i>=j)了，交换两个数在数组中的位置
            if(i < j) {
                int tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }
        }

        // 将基准数放到中间的位置（基准数归位）
        array[left] = array[i];
        array[i] = base;

        // 递归，继续向基准的左右两边执行和上面同样的操作
        // i的索引处为上面已确定好的基准值的位置，无需再处理
        quiklySort(array, left, i - 1);
        quiklySort(array, i + 1, right);
    }
    /**
     * 二分查找（思想：每一次都查找中间那个元素，比较大或者小就减少一半的元素，然后在新的有序表中查找中间那个元素，直到找到所要找的元素。）
     * (注意：二分查找需要先排序后才能进行)
     * @param arr1
     */
    private static int getPointByTwo(Integer[] arr1,int num){
        //二分法需要数组是一个有序数组
        insertSort(arr1);//插入排序法排序
        int first = 0;
        int last = arr1.length - 1;
        int middle = 0;
        //循环拆分比值
        while (first <= last){
            middle = first + (last - first)/2;
            //直接命中，则返回该值在数组的下标
            if(arr1[middle] == num){
                return middle;
            }else if(arr1[middle] > num){
                last = middle - 1;
            }else if(arr1[middle] < num){
                first = middle + 1;
            }
        }
        System.out.println("下标:"+middle+"  值:"+arr[middle]);
        return -1;
    }

    static String[] strArr = {"a","v","w","s","g","j","o","w","w","i","c","d","m","s","s","s","s"};

    /**
     * 查找出现次数最多的字母（思想：利用map的key值相同原理来累加出现次数）
     * @param arr1
     */
    private static void serchMost(String[] arr1){
        //接受结果集
        Map<String,Integer> maps = new HashMap<>();
        int index = arr1.length;
        //循环赋值
        for (int i = 0; i < index; i++) {
            //判断是否相同
            if(maps.containsKey(arr1[i])){
                maps.put(arr1[i],maps.get(arr1[i]) + 1);
            }else{
                maps.put(arr1[i],1);
            }
        }
        //获取key和value
        Set<Map.Entry<String,Integer>> setKeyAndValue = maps.entrySet();
        String keyTemp = null;
        int valueTemp = 0;
        for (Map.Entry en : setKeyAndValue){
            if((int)en.getValue() > valueTemp){
                valueTemp = (int)en.getValue();
                keyTemp = (String) en.getKey();
            }
        }
        System.out.println(valueTemp + keyTemp);
    }
    public static void main(String[] args) {
        quiklySort(arr,0,arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}
